home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / formats / gif / strtbl.txt < prev    next >
Encoding:
Text File  |  1988-03-21  |  4.0 KB  |  72 lines
  1. Non-Recursive String Table for LZW Decompressors - John Jeppson
  2.  
  3. The standard string table format, as suggested in "A Technique for High- 
  4. Performance Data Compression" by Terry A. Welch, is storage elements of the 
  5. form [prefix]K where [prefix] is a reference to an earlier string in the 
  6. table.  Character output then consists of looking up a string table entry and 
  7. generating the output string by recursive decomposition.  The characters come 
  8. off one at a time in reverse order, so are generally pushed on the stack and 
  9. copied off as a string, thereby correcting the order.  
  10.  
  11. The [prefix]K format is particularly well suited to compressors since it
  12. facilitates hashing methods for searching the table. Decompressors, on the
  13. other hand, never search the table so during decompression this format
  14. may not yield optimum performance.  This file discusses an alternative
  15. strategy for decompressors.
  16.  
  17. The trade-off is memory for speed.  Computationally intensive recursive 
  18. decomposition is not required, but the entire output charstream must be 
  19. retained in memory as an array of bytes.  The string table is implemented as 
  20. a table of pointers (and counts) to "earlier" strings already present in the 
  21. output stream.  Output for each received code is then a simple matter of 
  22. copying the string from an earlier site to the present site.  
  23.  
  24. If 'N' is the number of bits/pixel then the first 2**N strings in the string 
  25. table consist of a single character.  These single-character strings are
  26. the "root" codes and when first encountered do NOT previously exist in the
  27. output stream. All subsequent strings are at least two characters in length
  28. and do exist in the output charstream.
  29.  
  30. The string table should consist, therefore, of a set of 4096 records each 
  31. consisting of a pointer and an integer count.  (The longest possible string 
  32. is less than 4096 characters, so a 16-bit count will suffice.) The first 2**N 
  33. string table entries should be pointers to a separate static string array, 
  34. and each count should be 1.  This static string array can just be a 
  35. pre-initialized array [00,01,02...FE,FF] of byte.  Whenever a clear code is 
  36. encountered the string table should be cleared and re-initialized to these 
  37. root-string pointers.  
  38.  
  39. During decompression every code value received requires (1) a write of one or 
  40. more characters to the output stream, and (2) a new entry in the string table 
  41. (except for the first code).  The destination address and count of the 
  42. current write and of the previous write are retained and updated as 
  43. decompression proceeds.  
  44.  
  45. When a code is received there are two cases:
  46.  
  47. 1. value(code) already in string table.
  48.     (a) copy value(code) to the output charstream at curAddress.
  49.     (b) install previousAddress/previousCount+1 as the next entry in the 
  50. string table.  Note that by incrementing the count, the new string entry will 
  51. "overlap" onto the first character of the curAddress, which is just what we 
  52. want (i.e. [prefix]K ).
  53.  
  54. 2.  value(code) not yet in string table.
  55.     In this case we copy [prefix]K to the output charstream at curAddress.  
  56. Here [prefix] is the string at previousAddress/previousCount (from the 
  57. previous write operation) and K is the first character of that same string 
  58. (i.e., previousAddress[1]).  We then add curAddress/curCount as the next 
  59. entry in the string table.  
  60.  
  61. In every case we are simply copying a string of characters which should be 
  62. much faster than recursive decomposition.  It won't work, however, if the 
  63. output charstream is not retained in memory.  It also won't work, or at least 
  64. not gracefully, if the output charstream is maintained as small bitfields or 
  65. is broken up by intervening fill.  This might be true, for example, if the 
  66. output stream is sent directly to screen memory.  In those circumstances 
  67. recursive decomposition is the way to go.
  68.  
  69. With regard to the "root" string pointers, beware of relocation problems.
  70. These absolute addresses should be loaded dynamically whenever the string
  71. table is reset, they should never be hard coded into the application.
  72.